#define MAXHITS 1000

#include "crt/time.bi"
#include "crt/stdio.bi"

Enum CompareMethod
			BinaryCompare
			TextCompare
End Enum

Type _node	
	next_ As _node Ptr
	prev As _node Ptr
	hits(0 To MAXHITS) As Integer
	last_idx As Integer
End Type

Type _stringidx
	current As _node Ptr
	first As _node Ptr
	last As _node Ptr
	n As UInteger	
End Type


Declare Function init_idx(ByRef idx As _stringidx Ptr) As Integer
Declare Function StrIndex(ByRef source As String, ByRef pattern As String,ByRef stridx As _stringidx Ptr) As Integer
Declare Function destroy_idx(ByRef stridx As _stringidx Ptr) As Integer
Declare Function add_node_idx(ByRef stridx As _stringidx Ptr) As Integer		
Declare Function add_value_idx(ByVal value As Double,ByRef stridx As _stringidx Ptr) As Integer	
Declare Function StrReplace(	ByRef pSource As Const String													,_
								ByRef pFind As Const String													,_
								ByRef pReplaceWith As Const String											,_
								ByRef pReplacedCount As Integer = 0											,_
								ByVal pMaxReplacements As Const Integer = 0								,_
								ByVal pCompare As Const CompareMethod = BinaryCompare					)_
								As String

Function StrReplace(	ByRef pSource As Const String													,_
								ByRef pFind As Const String													,_
								ByRef pReplaceWith As Const String											,_
								ByRef pReplacedCount As Integer = 0											,_
								ByVal pMaxReplacements As Const Integer = 0								,_
								ByVal pCompare As Const CompareMethod = BinaryCompare					)_
								As String
	'{		
		Dim As Integer iPos, iReplacementLength, iFindLength
		Dim As Integer iRet, iDest, iSrc, iHidx, iRetLength
		Dim As String sRet, sTemp, sFind, sReplaceWith
		Dim As _stringidx Ptr Idx
		
		If pCompare = TextCompare Then
			sFind = LCase(pFind)
			sTemp = LCase(pSource)
			sReplaceWith = LCase(pReplaceWith)
		Else
			sFind = pFind
			sTemp = pSource
			sReplaceWith = pReplaceWith
		EndIf		
		
		pReplacedCount = 0
		iReplacementLength = Len(pReplaceWith)
		iPos = 1 - iReplacementLength
		iFindLength = Len(pFind)	
		iRet = StrIndex(sTemp,sFind,Idx)
		If (iRet = 0) Then						
			' If at least one replacement
			If (Idx->first->last_idx <> 0) Then								
				' prelude for construction of output
				Idx->current = Idx->first
				If (Idx->n = 1) Then										
					iRetLength = Idx->current->last_idx * iReplacementLength + Len(sTemp) - _
											 Idx->current->last_idx * iFindLength
				Else					
					'length of output = x * length of replacementpattern + 
					'										(length of sourcestring - x * length of findpattern)
					'										where x = number of times findpattern was found in input
					'										Formula can be notated shorter
					iRetLength = (((Idx->n-1) * MAXHITS) + Idx->last->last_idx) * iReplacementLength + _
											 (Len(sTemp) - (((Idx->n - 1) * MAXHITS) + Idx->last->last_idx) * iFindLength) 
											 
				End If
				sRet = String(iRetLength,0)				
				iPos = Idx->current->hits(0)
				iSrc = 1
				iDest = 1
				
				' start building the output
				While (Idx->n <> 0)
					' copy source to dest until match
					Mid(sRet,iDest) = Mid(sTemp,iSrc,iPos-iSrc)										
					' copy replace pattern to dest
					iDest += iPos - iSrc
					Mid(sRet,iDest) = sReplaceWith					
					iDest += iReplacementLength
					'skip matched pattern in source-string
					iSrc = iPos + iFindLength
					' if at last index in current index-node
					If (iHidx = Idx->current->last_idx - 1) Then
						Idx->n -= 1						
						If (Idx->n <> 0) Then							
							'jump to start of next index-node
							Idx->current = Idx->current->next_
							iHidx = 0
							iPos = Idx->current->hits(0)
						Else
							'no more matches, copy everything after final match to end of input-string
							If (Len(sTemp) > iPos) Then
								Mid(sRet,iDest) = Mid(sTemp,iSrc,Len(sTemp)-iSrc+1)
							End If
						End If
					Else
						' get next index from current index-node						
						iHidx += 1						
						iPos = Idx->current->hits(iHidx)						
					End If	
				Wend
				'done replacing, clean up and return result
				destroy_idx(Idx)
				Return sRet
			' no replacement, return input
			Else
				sRet = pSource
				destroy_idx(Idx)
				Return sRet
			End If		
		  'problem with memory, return source
		Else
			sRet = pSource
			Return sRet
		End If					
		' cannot get to this code, return sRet anyway
		Return sRet
	'}	
	End Function

Private Function init_idx(ByRef Idx As _stringidx Ptr) As Integer

/'Return values: 0 = no error
								 1 = out of memory
								 idx = pointer to new string index
'/	
	
	Dim Node As _node Ptr		
	
	Idx = New _stringidx
	If (Idx <> 0) Then
		Node = New _node
		If (node <> 0) Then
			Idx->last = Node
			Idx->first = Node
			Idx->current = Node
			Idx->current->last_idx = 0
			Idx->n = 1
			Return 0
		Else
			Return 1
		End If
	Else
		Return 1
	End If	
	ASSERT(Idx->n=1)
End Function

Public Function destroy_idx(ByRef stridx As _stringidx Ptr) As Integer
/'Pre - condition: stridx <> 0 '/

/'Return value: 0
'/

	If (stridx->current <> 0 AndAlso stridx->first <> 0 AndAlso stridx->last <> 0) Then
		stridx->current = stridx->first
		While (stridx->current->next_ <> 0)
			stridx->current = stridx->current->next_
			Delete stridx->current->prev			
		Wend
		If (stridx->current <> 0) Then
			Delete stridx->current
		End If
	End If	
	Delete stridx
	Return 0	

End Function

Private Function StrIndex(ByRef source As String, ByRef pattern As String,ByRef stridx As _stringidx Ptr) As Integer
/'Return values: 0 = no error								
								 1 = out of memory
								 stridx = pointer to string index
'/
	
	Dim As UInteger uSlength = Len(source)
	Dim As UInteger uPlength = Len(pattern)
	Dim As Integer iStart = 1	
	Dim As Integer iValue
	Dim As Integer iRes
	
	iRes= init_idx(stridx)
	If (iRes <> 1) Then
		iValue = Instr(iStart,source,pattern)
		While (iValue > 0) 				
			If (stridx->current->last_idx < MAXHITS) Then			
				stridx->current->hits(stridx->current->last_idx) = iValue	
				stridx->current->last_idx += 1					
			Else
				If (add_node_idx(stridx) <> 1) Then				
					stridx->current->hits(stridx->current->last_idx) = iValue
					stridx->current->last_idx += 1
				Else
					Return 1
				End If			
			End If							
			iStart = iValue + 1
			iValue = InStr(iStart,source,pattern)
		Wend
	Else
		Return 1
	End If		
	Return 0
End Function	


Private Function add_node_idx(ByRef stridx As _stringidx Ptr) As Integer

/' Pre condition: stridx <> 0 '/

/' Return values: 0 = no error
								  1 = out of memory
'/


	Dim Node As _node Ptr
	
	Node = New _node
	If (Node <> 0) Then		
		Node->prev = stridx->last
		Node->next_ = 0
		stridx->last->next_ = Node
		stridx->last = Node
		stridx->current = Node
		stridx->current->last_idx = 0
		stridx->n += 1		
		Return 0
	Else
		Return 1
	End If
End Function




Function main() As Integer

	Dim sRes As String
	Dim sStr As String
  Dim t1 As clock_t
	Dim t2 As clock_t

	
	Dim As zString Ptr file_
	Dim As FILE Ptr handle
	Dim As Integer handle2
	Dim As Integer length	

	Dim As Integer rep_count
	Dim As Integer max_rep = 0
	

	'GetThreadTimes(GetCurrentThread(), @ftDummy, @ftDummy, _
	'      @ftKernelTimeStart, @ftUserTimeStart)
	'Dim As FILETIME ftKernelTimeStart, ftKernelTimeEnd
	'Dim As FILETIME ftUserTimeStart,   ftUserTimeEnd
	'Dim As FILETIME ftDummy
	'Dim As SYSTEMTIME Start_user, Start_kernel, End_user, End_kernel
	'GetThreadTimes(GetCurrentThread(), @ftDummy, @ftDummy, _
	 '     @ftKernelTimeEnd, &ftUserTimeEnd)
	'FileTimeToSystemTime(@ftKernelTimeStart,@Start_Kernel)
	'FileTimeToSystemTime(@ftUserTimeStart,@Start_Sser)
	'FileTimeToSystemTime(@ftKernelTimeStart,@start_user)
	'FileTimeToSystemTime(@ftUserTimeStart,@end_user)
	 

	handle2 = FreeFile()
	Open "output" For Input As #handle2
	length = LOF(handle2)
	Close #handle2

	handle = fopen("output","r")
	file_ = CAllocate(length)
	fread(file_,length,SizeOf(Byte),handle)
	fflush(handle)

	'arg_= !"Lorem ipsum dolor sit amet,\nconsectetuer adipiscing elit,\rsed diam\r\nnonummy nibh..."
	sStr = *file_
	'arg_ = ""
	Print "Start"
	t1 = clock()
	'result = StrReplace("","","",rep_count,max_rep,BinaryCompare)
	'result = StrReverse(arg_)
	'result = StrRemoveChars(arg_,"s")
	'result = StrSubstring(arg_,1,len(arg_)-100)	
	sRes = StrReplace(sStr,"syntax","more dead people")	
	t2 = clock()
	Print "Done"
	Print t1
	Print t2	
	Print sRes;
	fclose(handle)
	Deallocate(file_)			
	Return 0
End Function


main()